Evolutionary dynamics has been classically studied for homogeneouspopulations, but now there is a growing interest in the non-homogenous case.One of the most important models has been proposed by Lieberman, Hauert andNowak, adapting to a weighted directed graph the classical process described byMoran. The Markov chain associated with the graph can be modified by erasingall non-trivial loops in its state space, obtaining the so-called EmbeddedMarkov chain (EMC). The fixation probability remains unchanged, but theexpected time to absorption (fixation or extinction) is reduced. In this paper,we shall use this idea to compute asymptotically the average fixationprobability for complete bipartite graphs. To this end, we firstly review somerecent results on evolutionary dynamics on graphs trying to clarify somepoints. We also revisit the 'Star Theorem' proved by Lieberman, Hauert andNowak for the star graphs. Theoretically, EMC techniques allow fast computationof the fixation probability, but in practice this is not always true. Thus, inthe last part of the paper, we compare this algorithm with the standard MonteCarlo method for some kind of complex networks.
展开▼
